package com.zlsy.learning.leetcode.sort;

import java.util.Arrays;

/**
 * @author zhouliang
 * @date 2020/8/25 16:50 归并排序演示
 */
public class MergeSort {

  public static void main(String[] args) {
    int[] a = new int[] {1, 5, 6, 2, 3, 4};
    //    int[] a = new int[] {10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
    //    int[] a = new int[] {10, 0, 2, 4, 6, 5, 7, 3, 8, 1, 9};
    int n = a.length;
    mergeSort(a, n);
  }

  private static void mergeSort(int[] a, int n) {
    mergeSortInternally(a, 0, n - 1);
    System.out.println(Arrays.toString(a));
  }

  private static void mergeSortInternally(int[] a, int p, int r) {
    if (p >= r) {
      return;
    }
    int q = p + (r - p) / 2;
    mergeSortInternally(a, p, q);
    mergeSortInternally(a, q + 1, r);
    //    merge(a, p, q, r);
    mergeBySentry(a, p, q, r);
  }

  private static void merge(int[] a, int p, int q, int r) {
    int i = p;
    int j = q + 1;
    int k = 0;
    int[] temp = new int[r - p + 1];
    while (i <= q && j <= r) {
      if (a[i] <= a[j]) {
        temp[k++] = a[i++];
      } else {
        temp[k++] = a[j++];
      }
    }
    // 判断哪个子数组中有剩余的数据
    int start = i;
    int end = q;
    if (j <= r) {
      start = j;
      end = r;
    }
    // 将剩余的数据拷贝到临时数组temp
    while (start <= end) {
      temp[k++] = a[start++];
    }
    // 将temp中的数组拷贝回A[p..............r];
    for (int l = 0; l <= r - p; l++) {
      a[p + l] = temp[l];
    }
  }

  /**
   * 基于哨兵模式的merge，代码比直接放入temp数组，再把temp数组拷贝进a简单点
   *
   * @param arr 分段后的数组
   * @param p 开始点
   * @param q 中间点
   * @param r 结束点
   */
  private static void mergeBySentry(int[] arr, int p, int q, int r) {
    // 定义拆分后两段的长度，每段都多定义一个长度作为哨兵
    int[] leftArr = new int[q - p + 2];
    int[] rightArr = new int[r - q + 1];

    // q - p + 1为除开哨兵的长度，哨兵的值定义为Integer.MAX_VALUE
    for (int i = 0; i < q - p + 1; i++) {
      leftArr[i] = arr[p + i];
    }
    leftArr[q - p + 1] = Integer.MAX_VALUE;

    // r-(q+1)+1为右边分段数组的长度
    for (int j = 0; j < r - q; j++) {
      rightArr[j] = arr[q + 1 + j];
    }
    rightArr[r - q] = Integer.MAX_VALUE;

    int i = 0;
    int j = 0;
    int k = p;
    // p到r比较然后放入arr
    while (k <= r) {
      if (leftArr[i] <= rightArr[j]) {
        arr[k++] = leftArr[i++];
      } else {
        arr[k++] = rightArr[j++];
      }
    }
  }
}
